The present invention relates to feedback shift registers. More specifically, the present invention relates to an exclusive OR (XOR) logic function of consecutive bits of a feedback shift register.
Long shift registers in general, and feedback shift registers in particular, are well established in the areas of digital electronics, and are used for numerous purposes. In particular, feedback shift registers (FSR) are used for the generation of pseudo-random series, in applications such as digital communication.
FIG. 1 is a circuit diagram of a conventional feedback shift register 100. Feedback shift register 100 implements a proposed scrambling function for the downlink of a 3rd generation telephony system. (See, 3GPP publication TS 25.213 V2.1.2, FIG. 14.)
Feedback shift register 100 includes a plurality of DQ flip-flops 1-18, which are connected in a chain, such that the Q output terminals of flip-flops 1-17 are connected to the D input terminals of flip-flops 2-18, respectively. Each of flip-flops 1-18 is clocked by a predetermined edge (e.g., the rising edges) of the same clock signal. As a result, binary data is shifted through the chain of flip-flops 1-18 in response to the clock signal.
The first flip-flop in the chain (i.e., flip-flop 1) receives a signal from a feedback function 23. In feedback shift register 100, feedback function 23 is a 4-input exclusive OR function, which has input terminals coupled to the Q output terminals of flip-flops 8, 11, 13 and 18.
Exclusive OR functions 21 and 22 provide a signal Q1 in response to other bits stored by feedback shift register 100. Signal Q1 is latched into DQ flip-flop 19. Exclusive OR function 21 is implemented by an 8-input exclusive OR device coupled to the Q output terminals of consecutive flip-flops 3-10. Exclusive OR function 22 is implemented by a 3-input exclusive OR device coupled to the output terminal of exclusive OR function 21 and to the Q output terminals of flip-flops 12 and 13.
In general, (Nxe2x88x921) 2-input exclusive OR gates are needed to implement an N-input exclusive OR function. Thus, seven 2-input exclusive OR gates are required to implement 8-input exclusive OR function 21. FIG. 2 is a circuit diagram of the seven 2-input exclusive OR gates 21A-21G used to implement 8-input exclusive OR function 21. For a reasonably fast implementation, exclusive OR gates 21A-21G are arranged in a three-level hierarchy, wherein exclusive OR gates 21A-21D are connected to form the first level, exclusive OR gates 21E-21F are connected to form the second level and exclusive OR gate 21G is connected to form the third level.
An exclusive OR gate is a relatively complex logic gate, with a CMOS implementation typically requiring 8 to 10 transistors. In addition, an exclusive OR gate has a significant signal propagation delay, which is roughly equivalent to twice the propagation delay of a simple logic gate. Thus, exclusive OR function 21 requires approximately 70 transistors and exhibits a signal propagation delay roughly equivalent to that of 6 simple logic gates.
It would therefore be desirable to have a structure that replaces a multiple-input exclusive OR function of a plurality of successive shift register bits and significantly reduces both transistor count and signal delay.
Accordingly, the present invention provides a circuit for implementing a function of a plurality of consecutive bits in a shift register. The circuit includes a 2-input logic gate having a first input terminal connected to receive a bit being shifted into the shift register, and a second input terminal coupled to receive a bit being shifted out of the shift register. The circuit further includes a sequential logic device having an input terminal coupled to an output terminal of the 2-input logic gate, an output terminal that provides the function, and a control terminal coupled to receive a control signal for resetting the sequential logic device.
In one embodiment, the 2-input logic gate is an exclusive OR gate, and the sequential logic device is a toggle flip-flop. In this embodiment, the function is a logical exclusive OR of the consecutive bits in the shift register. The function is implemented by resetting the output signal of the toggle flip flop when the consecutive bits of the shift register have a predetermined value (e.g., all logic xe2x80x9c1xe2x80x9d values). Then, the exclusive OR gate compares the bit to be shifted into the shift register with the bit to be shifted out of the shift register. The output signal of the toggle flip-flop is toggled if the exclusive OR gate indicates that no match exists. Conversely, the output signal of the toggle flip-flop remains unchanged if the exclusive OR gate indicates that a match exists.
The circuit constructed using the exclusive OR gate and the toggle flip-flop uses about 30 transistors and exhibits a delay of roughly 4 simple gates. Thus, this circuit has a significantly lower transistor requirement and a shorter signal delay than the prior art.
In other embodiments, functions other than an exclusive OR function of consecutive bits of a shift register can be implemented.
The present invention will be more fully understood in view of the following description and drawings.